/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/
#include <vector> 
#include "../graph/Graph.h"
#include <typeinfo>

using namespace std;

template <typename Tv> struct Vertex { 
   Tv data; int inDegree, outDegree; VStatus status; 
   int dTime, fTime; 
   int parent; int priority; 
   Vertex(Tv const & d = (Tv) 0) : 
   data(d), inDegree(0), outDegree(0), status(UNDISCOVERED),
      dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {} 
};

template <typename Te> struct Edge { 
   Te data; int weight; EStatus status; 
   Edge(Te const & d, int w) : data(d), weight(w), status(UNDETERMINED) {} 
};

template <typename Tv, typename Te> 
class GraphMatrix : public Graph<Tv, Te> { 
private:
   vector< Vertex<Tv> > V; 
   vector< vector<Edge<Te>*> > E; 
public:
   GraphMatrix() { this->n = this->e = 0; } 
   ~GraphMatrix() { 
      for (int j = 0; j < this->n; j++)  
         for (int k = 0; k < this->n; k++) 
            delete E[j][k]; 
   }

   virtual Tv& vertex(int i) { return V[i].data; } 
   virtual int inDegree(int i) { return V[i].inDegree; } 
   virtual int outDegree(int i) { return V[i].outDegree; } 
   virtual int firstNbr(int i) { return nextNbr(i, this->n); } 
   virtual int nextNbr(int i, int j) 
   { while ((-1 < j) && (!exists(i, --j))); return j; } 
   virtual VStatus& status(int i) { return V[i].status; } 
   virtual int& dTime(int i) { return V[i].dTime; } 
   virtual int& fTime(int i) { return V[i].fTime; } 
   virtual int& parent(int i) { return V[i].parent; } 
   virtual int& priority(int i) { return V[i].priority; } 

   virtual int insert(Tv const & vertex) { //插入节点
      for (int j = 0; j < this->n; j++) 
		  //E[j].insert(NULL); 
		  E[j].push_back(NULL);
	  this->n++; 
      //E.insert(vector<Edge<Te>*>(n, n, (Edge<Te>*) NULL));
	  E.push_back(vector<Edge<Te>*>(this->n,(Edge<Te>*) NULL));
      //return V.insert(Vertex<Tv>(vertex));  //向量类模板插入一个元素就是插入到末尾
	  return V.push_back(Vertex<Tv>(vertex));
   }
   virtual Tv remove(int i) { 
      for (int j = 0; j < this->n; j++) 
         if (exists(i, j)) { delete E[i][j]; V[j].inDegree--; } 
      E.remove(i); this->n--; 
      for (int j = 0; j < this->n; j++) 
         if (exists(j, i)) { delete E[j].remove(i); V[j].outDegree--; } 
      Tv vBak = vertex(i); V.remove(i); 
      return vBak; 
   }

   virtual bool exists(int i, int j) 
   { return (0 <= i) && (i < this->n) && (0 <= j) && (j < this->n) && E[i][j] != NULL; }

   virtual EStatus& status(int i, int j) { return E[i][j]->status; } 
   virtual Te& edge(int i, int j) { return E[i][j]->data; } 
   virtual int& weight(int i, int j) { return E[i][j]->weight; } 

   virtual void insert(Te const & edge, int w, int i, int j) { //插入边
      if (exists(i, j)) return; 
      E[i][j] = new Edge<Te>(edge, w); 
     this-> e++; V[i].outDegree++; V[j].inDegree++; 
   }
   virtual Te remove(int i, int j) { 
      Te eBak = edge(i, j); delete E[i][j]; E[i][j] = NULL; 
      this->e--; V[i].outDegree--; V[j].inDegree--; 
      return eBak; 
   }
};


template <typename Tv, typename Te> 
void GraphMatrix_print(GraphMatrix<Tv, Te>& s) { 
   int inD = 0; for (int i = 0; i < s.n; i++) inD += s.inDegree(i);
   int outD = 0; for (int i = 0; i < s.n; i++) outD += s.outDegree(i);
   printf("%s[%d]*(%d, %d):\n", typeid(s).name(), &s, s.n, s.e); 

   printf("%d",s.n); printf(" "); printf("%d",inD); printf("|");
   for (int i = 0; i < s.n; i++) { cout<<s.vertex(i); printf("["); cout<<s.status(i); printf("] "); }
   printf("\n");

   printf("%d",outD); printf(" "); printf("%d",s.e); printf("|");
   for (int i = 0; i < s.n; i++) { printf("%d",s.inDegree(i)); printf(" "); }
   printf("| dTime fTime Parent Weight\n");

   printf("-----------+"); for (int i = 0; i < s.n; i++) printf("------");
   printf("+----------------------------\n");

   for (int i = 0; i < s.n; i++) {
      cout<<s.vertex(i); printf("["); cout<<s.status(i); printf("] "); printf("%d",s.outDegree(i)); printf("|");
      for (int j = 0; j < s.n; j++)
         if (s.exists(i, j)) { printf("%d",s.edge(i, j)); cout<<s.status(i, j); }
         else printf("     .");
      printf("| "); printf("%d",s.dTime(i)); printf(" "); printf("%d",s.fTime(i));
      printf("     "); if (0 > s.parent(i)) cout<<"^"; else cout<<s.vertex(s.parent(i));
      printf("  "); if (INT_MAX > s.priority(i)) printf("%d",s.priority(i)); else cout<<" INF";
      printf("\n");
   }
   printf("\n");
}
